package leetcode

import (
	"gitee.com/ombak/leetcode/pkg/list"
)

var left *list.ListNode

// IsPalindromeByTraverse https://leetcode.com/problems/palindrome-linked-list/
func isPalindromeByTraverse(head *list.ListNode) bool {
	left = head
	return traverse(head)
}

func traverse(right *list.ListNode) bool {
	if right == nil {
		return true
	}
	// last element value
	result := traverse(right.Next)
	result = result && (left.Val == right.Val)
	left = left.Next
	return result
}

// IsPalindromeByTraverse https://leetcode.com/problems/palindrome-linked-list/
func isPalindromeByReverse2(head *list.ListNode) bool {
	// first: find the middle node of linked list
	f, s := head, head
	for f != nil && f.Next != nil {
		f = f.Next.Next
		s = s.Next // its middle node
	}
	// second: define left and right node
	left, left2 := head, s
	if f != nil {
		left2 = s.Next
	}
	right := reverse(left2)
	// third: compare pointer a with pointer b
	for right != nil {
		if left.Val != right.Val {
			return false
		}
		right = right.Next
		left = left.Next
	}
	// finish: its a palindrome
	return true
}

func reverse(head *list.ListNode) *list.ListNode {
	cur := head
	var pre *list.ListNode
	pre = nil
	for cur != nil {
		nx := cur.Next
		cur.Next = pre
		pre = cur
		cur = nx
	}
	return pre
}
